home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 008a / perl40_2.zip / REGCOMP.C < prev    next >
C/C++ Source or Header  |  1991-11-28  |  33KB  |  1,527 lines
  1. /* NOTE: this is derived from Henry Spencer's regexp code, and should not
  2.  * confused with the original package (see point 3 below).  Thanks, Henry!
  3.  */
  4.  
  5.  
  6. /* Additional note: this code is very heavily munged from Henry's version
  7.  * in places.  In some spots I've traded clarity for efficiency, so don't
  8.  * blame Henry for some of the lack of readability.
  9.  */
  10.  
  11.  
  12. /* $RCSfile: regcomp.c,v $$Revision: 4.0.1.4 $$Date: 91/11/05 22:55:14 $
  13.  *
  14.  * $Log:    regcomp.c,v $
  15.  * Revision 4.0.1.4  91/11/05  22:55:14  lwall
  16.  * patch11: Erratum
  17.  *
  18.  * Revision 4.0.1.3  91/11/05  18:22:28  lwall
  19.  * patch11: minimum match length calculation in regexp is now cumulative
  20.  * patch11: initial .* in pattern had dependency on value of $*
  21.  * patch11: certain patterns made use of garbage pointers from uncleared memory
  22.  * patch11: prepared for ctype implementations that don't define isascii()
  23.  *
  24.  * Revision 4.0.1.2  91/06/07  11:48:24  lwall
  25.  * patch4: new copyright notice
  26.  * patch4: /(x+) \1/ incorrectly optimized to not match "xxx xx"
  27.  * patch4: // wouldn't use previous pattern if it started with a null character
  28.  *
  29.  * Revision 4.0.1.1  91/04/12  09:04:45  lwall
  30.  * patch1: random cleanup in cpp namespace
  31.  *
  32.  * Revision 4.0  91/03/20  01:39:01  lwall
  33.  * 4.0 baseline.
  34.  *
  35.  */
  36. /*SUPPRESS 112*/
  37. /*
  38.  * regcomp and regexec -- regsub and regerror are not used in perl
  39.  *
  40.  *    Copyright (c) 1986 by University of Toronto.
  41.  *    Written by Henry Spencer.  Not derived from licensed software.
  42.  *
  43.  *    Permission is granted to anyone to use this software for any
  44.  *    purpose on any computer system, and to redistribute it freely,
  45.  *    subject to the following restrictions:
  46.  *
  47.  *    1. The author is not responsible for the consequences of use of
  48.  *        this software, no matter how awful, even if they arise
  49.  *        from defects in it.
  50.  *
  51.  *    2. The origin of this software must not be misrepresented, either
  52.  *        by explicit claim or by omission.
  53.  *
  54.  *    3. Altered versions must be plainly marked as such, and must not
  55.  *        be misrepresented as being the original software.
  56.  *
  57.  *
  58.  ****    Alterations to Henry's code are...
  59.  ****
  60.  ****    Copyright (c) 1991, Larry Wall
  61.  ****
  62.  ****    You may distribute under the terms of either the GNU General Public
  63.  ****    License or the Artistic License, as specified in the README file.
  64.  
  65.  
  66.  *
  67.  * Beware that some of this code is subtly aware of the way operator
  68.  * precedence is structured in regular expressions.  Serious changes in
  69.  * regular-expression syntax might require a total rethink.
  70.  */
  71. #include "EXTERN.h"
  72. #include "perl.h"
  73. #include "INTERN.h"
  74. #include "regcomp.h"
  75.  
  76.  
  77. #ifdef MSDOS
  78. # if defined(BUGGY_MSC6)
  79.  /* MSC 6.00A breaks on op/regexp.t test 85 unless we turn this off */
  80.  # pragma optimize("a",off)
  81.  /* But MSC 6.00A is happy with 'w', for aliases only across function calls*/
  82.  # pragma optimize("w",on )
  83. # endif /* BUGGY_MSC6 */
  84. #endif /* MSDOS */
  85.  
  86.  
  87. #ifndef STATIC
  88. #define    STATIC    static
  89. #endif
  90.  
  91.  
  92. #define    ISMULT1(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  93. #define    ISMULT2(s)    ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
  94.     ((*s) == '{' && regcurly(s)))
  95. #define    META    "^$.[()|?+*\\"
  96.  
  97.  
  98. #ifdef SPSTART
  99. #undef SPSTART        /* dratted cpp namespace... */
  100. #endif
  101. /*
  102.  * Flags to be passed up and down.
  103.  */
  104. #define    HASWIDTH    01    /* Known never to match null string. */
  105. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  106. #define    SPSTART        04    /* Starts with * or +. */
  107. #define    WORST        0    /* Worst case. */
  108.  
  109.  
  110. /*
  111.  * Global work variables for regcomp().
  112.  */
  113. static char *regprecomp;        /* uncompiled string. */
  114. static char *regparse;        /* Input-scan pointer. */
  115. static char *regxend;        /* End of input for compile */
  116. static int regnpar;        /* () count. */
  117. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  118. static long regsize;        /* Code size. */
  119. static int regfold;
  120. static int regsawbracket;    /* Did we do {d,d} trick? */
  121. static int regsawback;        /* Did we see \1, ...? */
  122.  
  123.  
  124. /*
  125.  * Forward declarations for regcomp()'s friends.
  126.  */
  127. STATIC int regcurly();
  128. STATIC char *reg();
  129. STATIC char *regbranch();
  130. STATIC char *regpiece();
  131. STATIC char *regatom();
  132. STATIC char *regclass();
  133. STATIC char *regnode();
  134. STATIC char *reganode();
  135. STATIC void regc();
  136. STATIC void reginsert();
  137. STATIC void regtail();
  138. STATIC void regoptail();
  139.  
  140.  
  141. /*
  142.  - regcomp - compile a regular expression into internal code
  143.  *
  144.  * We can't allocate space until we know how big the compiled form will be,
  145.  * but we can't compile it (and thus know how big it is) until we've got a
  146.  * place to put the code.  So we cheat:  we compile it twice, once with code
  147.  * generation turned off and size counting turned on, and once "for real".
  148.  * This also means that we don't allocate space until we are sure that the
  149.  * thing really will compile successfully, and we never have to move the
  150.  * code and thus invalidate pointers into it.  (Note that it has to be in
  151.  * one piece because free() must be able to free it all.) [NB: not true in perl]
  152.  *
  153.  * Beware that the optimization-preparation code in here knows about some
  154.  * of the structure of the compiled regexp.  [I'll say.]
  155.  */
  156. regexp *
  157. regcomp(exp,xend,fold)
  158. char *exp;
  159. char *xend;
  160. int fold;
  161. {
  162.     register regexp *r;
  163.     register char *scan;
  164.     register STR *longish;
  165.     STR *longest;
  166.     register int len;
  167.     register char *first;
  168.     int flags;
  169.     int backish;
  170.     int backest;
  171.     int curback;
  172.     int minlen;
  173. #ifndef safemalloc
  174.     extern char *safemalloc();
  175. #endif
  176.     extern char *savestr();
  177.     int sawplus = 0;
  178.     int sawopen = 0;
  179.  
  180.  
  181.     if (exp == NULL)
  182.         fatal("NULL regexp argument");
  183.  
  184.  
  185.     /* First pass: determine size, legality. */
  186.     regfold = fold;
  187.     regparse = exp;
  188.     regxend = xend;
  189.     regprecomp = nsavestr(exp,xend-exp);
  190.     regsawbracket = 0;
  191.     regsawback = 0;
  192.     regnpar = 1;
  193.     regsize = 0L;
  194.     regcode = ®dummy;
  195.     regc((char)MAGIC);
  196.     if (reg(0, &flags) == NULL) {
  197.         Safefree(regprecomp);
  198.         regprecomp = Nullch;
  199.         return(NULL);
  200.     }
  201.  
  202.  
  203.     /* Small enough for pointer-storage convention? */
  204.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  205.         FAIL("regexp too big");
  206.  
  207.  
  208.     /* Allocate space. */
  209.     Newc(1001, r, sizeof(regexp) + (unsigned)regsize, char, regexp);
  210.     if (r == NULL)
  211.         FAIL("regexp out of space");
  212.  
  213.  
  214.     /* Second pass: emit code. */
  215.     if (regsawbracket)
  216.         bcopy(regprecomp,exp,xend-exp);
  217.     r->prelen = xend-exp;
  218.     r->precomp = regprecomp;
  219.     r->subbeg = r->subbase = NULL;
  220.     regparse = exp;
  221.     regnpar = 1;
  222.     regcode = r->program;
  223.     regc((char)MAGIC);
  224.     if (reg(0, &flags) == NULL)
  225.         return(NULL);
  226.  
  227.  
  228.     /* Dig out information for optimizations. */
  229.     r->regstart = Nullstr;    /* Worst-case defaults. */
  230.     r->reganch = 0;
  231.     r->regmust = Nullstr;
  232.     r->regback = -1;
  233.     r->regstclass = Nullch;
  234.     scan = r->program+1;            /* First BRANCH. */
  235.     if (OP(regnext(scan)) == END) {/* Only one top-level choice. */
  236.         scan = NEXTOPER(scan);
  237.  
  238.  
  239.         first = scan;
  240.         while ((OP(first) == OPEN && (sawopen = 1)) ||
  241.             (OP(first) == BRANCH && OP(regnext(first)) != BRANCH) ||
  242.             (OP(first) == PLUS) ||
  243.             (OP(first) == CURLY && ARG1(first) > 0) ) {
  244.             if (OP(first) == PLUS)
  245.                 sawplus = 1;
  246.             else
  247.                 first += regarglen[OP(first)];
  248.             first = NEXTOPER(first);
  249.         }
  250.  
  251.  
  252.         /* Starting-point info. */
  253.         again:
  254.         if (OP(first) == EXACTLY) {
  255.             r->regstart =
  256.                 str_make(OPERAND(first)+1,*OPERAND(first));
  257.             if (r->regstart->str_cur > !(sawstudy|fold))
  258.                 fbmcompile(r->regstart,fold);
  259.         }
  260.         else if ((exp = index(simple,OP(first))) && exp > simple)
  261.             r->regstclass = first;
  262.         else if (OP(first) == BOUND || OP(first) == NBOUND)
  263.             r->regstclass = first;
  264.         else if (OP(first) == BOL ||
  265.             (OP(first) == STAR && OP(NEXTOPER(first)) == ANY) ) {
  266.             /* kinda turn .* into ^.* */
  267.             r->reganch = ROPT_ANCH | ROPT_IMPLICIT;
  268.             first = NEXTOPER(first);
  269.                 goto again;
  270.         }
  271.         if (sawplus && (!sawopen || !regsawback))
  272.             r->reganch |= ROPT_SKIP;    /* x+ must match 1st of run */
  273.  
  274.  
  275. #ifdef DEBUGGING
  276.         if (debug & 512)
  277.             fprintf(stderr,"first %d next %d offset %d\n",
  278.               OP(first), OP(NEXTOPER(first)), first - scan);
  279. #endif
  280.         /*
  281.          * If there's something expensive in the r.e., find the
  282.          * longest literal string that must appear and make it the
  283.          * regmust.  Resolve ties in favor of later strings, since
  284.          * the regstart check works with the beginning of the r.e.
  285.          * and avoiding duplication strengthens checking.  Not a
  286.          * strong reason, but sufficient in the absence of others.
  287.          * [Now we resolve ties in favor of the earlier string if
  288.          * it happens that curback has been invalidated, since the
  289.          * earlier string may buy us something the later one won't.]
  290.          */
  291.         longish = str_make("",0);
  292.         longest = str_make("",0);
  293.         len = 0;
  294.         minlen = 0;
  295.         curback = 0;
  296.         backish = 0;
  297.         backest = 0;
  298.         while (OP(scan) != END) {
  299.             if (OP(scan) == BRANCH) {
  300.                 if (OP(regnext(scan)) == BRANCH) {
  301.                 curback = -30000;
  302.                 while (OP(scan) == BRANCH)
  303.                     scan = regnext(scan);
  304.                 }
  305.                 else    /* single branch is ok */
  306.                 scan = NEXTOPER(scan);
  307.             }
  308.             if (OP(scan) == EXACTLY) {
  309.                 char *t;
  310.  
  311.  
  312.                 first = scan;
  313.                 while (OP(t = regnext(scan)) == CLOSE)
  314.                 scan = t;
  315.                 minlen += *OPERAND(first);
  316.                 if (curback - backish == len) {
  317.                 str_ncat(longish, OPERAND(first)+1,
  318.                     *OPERAND(first));
  319.                 len += *OPERAND(first);
  320.                 curback += *OPERAND(first);
  321.                 first = regnext(scan);
  322.                 }
  323.                 else if (*OPERAND(first) >= len + (curback >= 0)) {
  324.                 len = *OPERAND(first);
  325.                 str_nset(longish, OPERAND(first)+1,len);
  326.                 backish = curback;
  327.                 curback += len;
  328.                 first = regnext(scan);
  329.                 }
  330.                 else
  331.                 curback += *OPERAND(first);
  332.             }
  333.             else if (index(varies,OP(scan))) {
  334.                 curback = -30000;
  335.                 len = 0;
  336.                 if (longish->str_cur > longest->str_cur) {
  337.                 str_sset(longest,longish);
  338.                 backest = backish;
  339.                 }
  340.                 str_nset(longish,"",0);
  341.                 if (OP(scan) == PLUS &&
  342.                   index(simple,OP(NEXTOPER(scan))))
  343.                 minlen++;
  344.                 else if (OP(scan) == CURLY &&
  345.                   index(simple,OP(NEXTOPER(scan)+4)))
  346.                 minlen += ARG1(scan);
  347.             }
  348.             else if (index(simple,OP(scan))) {
  349.                 curback++;
  350.                 minlen++;
  351.                 len = 0;
  352.                 if (longish->str_cur > longest->str_cur) {
  353.                 str_sset(longest,longish);
  354.                 backest = backish;
  355.                 }
  356.                 str_nset(longish,"",0);
  357.             }
  358.             scan = regnext(scan);
  359.         }
  360.  
  361.  
  362.         /* Prefer earlier on tie, unless we can tail match latter */
  363.  
  364.  
  365.         if (longish->str_cur + (OP(first) == EOL) > longest->str_cur) {
  366.             str_sset(longest,longish);
  367.             backest = backish;
  368.         }
  369.         else
  370.             str_nset(longish,"",0);
  371.         if (longest->str_cur
  372.             &&
  373.             (!r->regstart
  374.              ||
  375.              !fbminstr((unsigned char*) r->regstart->str_ptr,
  376.               (unsigned char *) r->regstart->str_ptr
  377.                 + r->regstart->str_cur,
  378.               longest)
  379.             )
  380.            )
  381.         {
  382.             r->regmust = longest;
  383.             if (backest < 0)
  384.                 backest = -1;
  385.             r->regback = backest;
  386.             if (longest->str_cur
  387.               > !(sawstudy || fold || OP(first) == EOL) )
  388.                 fbmcompile(r->regmust,fold);
  389.             r->regmust->str_u.str_useful = 100;
  390.             if (OP(first) == EOL && longish->str_cur)
  391.                 r->regmust->str_pok |= SP_TAIL;
  392.         }
  393.         else {
  394.             str_free(longest);
  395.             longest = Nullstr;
  396.         }
  397.         str_free(longish);
  398.     }
  399.  
  400.  
  401.     r->do_folding = fold;
  402.     r->nparens = regnpar - 1;
  403.     r->minlen = minlen;
  404.     Newz(1002, r->startp, regnpar, char*);
  405.     Newz(1002, r->endp, regnpar, char*);
  406. #ifdef DEBUGGING
  407.     if (debug & 512)
  408.         regdump(r);
  409. #endif
  410.     return(r);
  411. }
  412.  
  413.  
  414. /*
  415.  - reg - regular expression, i.e. main body or parenthesized thing
  416.  *
  417.  * Caller must absorb opening parenthesis.
  418.  *
  419.  * Combining parenthesis handling with the base level of regular expression
  420.  * is a trifle forced, but the need to tie the tails of the branches to what
  421.  * follows makes it hard to avoid.
  422.  */
  423. static char *
  424. reg(paren, flagp)
  425. int paren;            /* Parenthesized? */
  426. int *flagp;
  427. {
  428.     register char *ret;
  429.     register char *br;
  430.     register char *ender;
  431.     register int parno;
  432.     int flags;
  433.  
  434.  
  435.     *flagp = HASWIDTH;    /* Tentatively. */
  436.  
  437.  
  438.     /* Make an OPEN node, if parenthesized. */
  439.     if (paren) {
  440.         parno = regnpar;
  441.         regnpar++;
  442.         ret = reganode(OPEN, parno);
  443.     } else
  444.         ret = NULL;
  445.  
  446.  
  447.     /* Pick up the branches, linking them together. */
  448.     br = regbranch(&flags);
  449.     if (br == NULL)
  450.         return(NULL);
  451.     if (ret != NULL)
  452.         regtail(ret, br);    /* OPEN -> first. */
  453.     else
  454.         ret = br;
  455.     if (!(flags&HASWIDTH))
  456.         *flagp &= ~HASWIDTH;
  457.     *flagp |= flags&SPSTART;
  458.     while (*regparse == '|') {
  459.         regparse++;
  460.         br = regbranch(&flags);
  461.         if (br == NULL)
  462.             return(NULL);
  463.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  464.         if (!(flags&HASWIDTH))
  465.             *flagp &= ~HASWIDTH;
  466.         *flagp |= flags&SPSTART;
  467.     }
  468.  
  469.  
  470.     /* Make a closing node, and hook it on the end. */
  471.     if (paren)
  472.         ender = reganode(CLOSE, parno);
  473.     else
  474.         ender = regnode(END);
  475.     regtail(ret, ender);
  476.  
  477.  
  478.     /* Hook the tails of the branches to the closing node. */
  479.     for (br = ret; br != NULL; br = regnext(br))
  480.         regoptail(br, ender);
  481.  
  482.  
  483.     /* Check for proper termination. */
  484.     if (paren && *regparse++ != ')') {
  485.         FAIL("unmatched () in regexp");
  486.     } else if (!paren && regparse < regxend) {
  487.         if (*regparse == ')') {
  488.             FAIL("unmatched () in regexp");
  489.         } else
  490.             FAIL("junk on end of regexp");    /* "Can't happen". */
  491.         /* NOTREACHED */
  492.     }
  493.  
  494.  
  495.     return(ret);
  496. }
  497.  
  498.  
  499. /*
  500.  - regbranch - one alternative of an | operator
  501.  *
  502.  * Implements the concatenation operator.
  503.  */
  504. static char *
  505. regbranch(flagp)
  506. int *flagp;
  507. {
  508.     register char *ret;
  509.     register char *chain;
  510.     register char *latest;
  511.     int flags;
  512.  
  513.  
  514.     *flagp = WORST;        /* Tentatively. */
  515.  
  516.  
  517.     ret = regnode(BRANCH);
  518.     chain = NULL;
  519.     while (regparse < regxend && *regparse != '|' && *regparse != ')') {
  520.         latest = regpiece(&flags);
  521.         if (latest == NULL)
  522.             return(NULL);
  523.         *flagp |= flags&HASWIDTH;
  524.         if (chain == NULL)    /* First piece. */
  525.             *flagp |= flags&SPSTART;
  526.         else
  527.             regtail(chain, latest);
  528.         chain = latest;
  529.     }
  530.     if (chain == NULL)    /* Loop ran zero times. */
  531.         (void) regnode(NOTHING);
  532.  
  533.  
  534.     return(ret);
  535. }
  536.  
  537.  
  538. /*
  539.  - regpiece - something followed by possible [*+?]
  540.  *
  541.  * Note that the branching code sequences used for ? and the general cases
  542.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  543.  * both the endmarker for their branch list and the body of the last branch.
  544.  * It might seem that this node could be dispensed with entirely, but the
  545.  * endmarker role is not redundant.
  546.  */
  547. static char *
  548. regpiece(flagp)
  549. int *flagp;
  550. {
  551.     register char *ret;
  552.     register char op;
  553.     register char *next;
  554.     int flags;
  555.     char *origparse = regparse;
  556.     int orignpar = regnpar;
  557.     char *max;
  558.     int iter;
  559.     char ch;
  560.  
  561.  
  562.     ret = regatom(&flags);
  563.     if (ret == NULL)
  564.         return(NULL);
  565.  
  566.  
  567.     op = *regparse;
  568.  
  569.  
  570.     /* Here's a total kludge: if after the atom there's a {\d+,?\d*}
  571.      * then we decrement the first number by one and reset our
  572.      * parsing back to the beginning of the same atom.  If the first number
  573.      * is down to 0, decrement the second number instead and fake up
  574.      * a ? after it.  Given the way this compiler doesn't keep track
  575.      * of offsets on the first pass, this is the only way to replicate
  576.      * a piece of code.  Sigh.
  577.      */
  578.     if (op == '{' && regcurly(regparse)) {
  579.         next = regparse + 1;
  580.         max = Nullch;
  581.         while (isDIGIT(*next) || *next == ',') {
  582.         if (*next == ',') {
  583.             if (max)
  584.             break;
  585.             else
  586.             max = next;
  587.         }
  588.         next++;
  589.         }
  590.         if (*next == '}') {        /* got one */
  591.         if (!max)
  592.             max = next;
  593.         regparse++;
  594.         iter = atoi(regparse);
  595.         if (flags&SIMPLE) {    /* we can do it right after all */
  596.             int tmp;
  597.  
  598.  
  599.             reginsert(CURLY, ret);
  600.             if (iter > 0)
  601.             *flagp = (WORST|HASWIDTH);
  602.             if (*max == ',')
  603.             max++;
  604.             else
  605.             max = regparse;
  606.             tmp = atoi(max);
  607.             if (tmp && tmp < iter)
  608.             fatal("Can't do {n,m} with n > m");
  609.             if (regcode != ®dummy) {
  610. #ifdef REGALIGN
  611.             *(unsigned short *)(ret+3) = iter;
  612.             *(unsigned short *)(ret+5) = tmp;
  613. #else
  614.             ret[3] = iter >> 8; ret[4] = iter & 0377;
  615.             ret[5] = tmp  >> 8; ret[6] = tmp  & 0377;
  616. #endif
  617.             }
  618.             regparse = next;
  619.             goto nest_check;
  620.         }
  621.         regsawbracket++;    /* remember we clobbered exp */
  622.         if (iter > 0) {
  623.             ch = *max;
  624.             sprintf(regparse,"%.*d", max-regparse, iter - 1);
  625.             *max = ch;
  626.             if (*max == ',' && max[1] != '}') {
  627.             if (atoi(max+1) <= 0)
  628.                 fatal("Can't do {n,m} with n > m");
  629.             ch = *next;
  630.             sprintf(max+1,"%.*d", next-(max+1), atoi(max+1) - 1);
  631.             *next = ch;
  632.             }
  633.             if (iter != 1 || *max == ',') {
  634.             regparse = origparse;    /* back up input pointer */
  635.             regnpar = orignpar;    /* don't make more parens */
  636.             }
  637.             else {
  638.             regparse = next;
  639.             goto nest_check;
  640.             }
  641.             *flagp = flags;
  642.             return ret;
  643.         }
  644.         if (*max == ',') {
  645.             max++;
  646.             iter = atoi(max);
  647.             if (max == next) {        /* any number more? */
  648.             regparse = next;
  649.             op = '*';        /* fake up one with a star */
  650.             }
  651.             else if (iter > 0) {
  652.             op = '?';        /* fake up optional atom */
  653.             ch = *next;
  654.             sprintf(max,"%.*d", next-max, iter - 1);
  655.             *next = ch;
  656.             if (iter == 1)
  657.                 regparse = next;
  658.             else {
  659.                 regparse = origparse - 1; /* offset ++ below */
  660.                 regnpar = orignpar;
  661.             }
  662.             }
  663.             else
  664.             fatal("Can't do {n,0}");
  665.         }
  666.         else
  667.             fatal("Can't do {0}");
  668.         }
  669.     }
  670.  
  671.  
  672.     if (!ISMULT1(op)) {
  673.         *flagp = flags;
  674.         return(ret);
  675.     }
  676.  
  677.  
  678.     if (!(flags&HASWIDTH) && op != '?')
  679.         FAIL("regexp *+ operand could be empty");
  680.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  681.  
  682.  
  683.     if (op == '*' && (flags&SIMPLE))
  684.         reginsert(STAR, ret);
  685.     else if (op == '*') {
  686.         /* Emit x* as (x&|), where & means "self". */
  687.         reginsert(BRANCH, ret);            /* Either x */
  688.         regoptail(ret, regnode(BACK));        /* and loop */
  689.         regoptail(ret, ret);            /* back */
  690.         regtail(ret, regnode(BRANCH));        /* or */
  691.         regtail(ret, regnode(NOTHING));        /* null. */
  692.     } else if (op == '+' && (flags&SIMPLE))
  693.         reginsert(PLUS, ret);
  694.     else if (op == '+') {
  695.         /* Emit x+ as x(&|), where & means "self". */
  696.         next = regnode(BRANCH);            /* Either */
  697.         regtail(ret, next);
  698.         regtail(regnode(BACK), ret);        /* loop back */
  699.         regtail(next, regnode(BRANCH));        /* or */
  700.         regtail(ret, regnode(NOTHING));        /* null. */
  701.     } else if (op == '?') {
  702.         /* Emit x? as (x|) */
  703.         reginsert(BRANCH, ret);            /* Either x */
  704.         regtail(ret, regnode(BRANCH));        /* or */
  705.         next = regnode(NOTHING);        /* null. */
  706.         regtail(ret, next);
  707.         regoptail(ret, next);
  708.     }
  709.       nest_check:
  710.     regparse++;
  711.     if (ISMULT2(regparse))
  712.         FAIL("nested *?+ in regexp");
  713.  
  714.  
  715.     return(ret);
  716. }
  717.  
  718.  
  719. /*
  720.  - regatom - the lowest level
  721.  *
  722.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  723.  * it can turn them into a single node, which is smaller to store and
  724.  * faster to run.  Backslashed characters are exceptions, each becoming a
  725.  * separate node; the code is simpler that way and it's not worth fixing.
  726.  *
  727.  * [Yes, it is worth fixing, some scripts can run twice the speed.]
  728.  */
  729. static char *
  730. regatom(flagp)
  731. int *flagp;
  732. {
  733.     register char *ret;
  734.     int flags;
  735.  
  736.  
  737.     *flagp = WORST;        /* Tentatively. */
  738.  
  739.  
  740.     switch (*regparse++) {
  741.     case '^':
  742.         ret = regnode(BOL);
  743.         break;
  744.     case '$':
  745.         ret = regnode(EOL);
  746.         break;
  747.     case '.':
  748.         ret = regnode(ANY);
  749.         *flagp |= HASWIDTH|SIMPLE;
  750.         break;
  751.     case '[':
  752.         ret = regclass();
  753.         *flagp |= HASWIDTH|SIMPLE;
  754.         break;
  755.     case '(':
  756.         ret = reg(1, &flags);
  757.         if (ret == NULL)
  758.             return(NULL);
  759.         *flagp |= flags&(HASWIDTH|SPSTART);
  760.         break;
  761.     case '|':
  762.     case ')':
  763.         FAIL("internal urp in regexp");    /* Supposed to be caught earlier. */
  764.         break;
  765.     case '?':
  766.     case '+':
  767.     case '*':
  768.         FAIL("?+* follows nothing in regexp");
  769.         break;
  770.     case '\\':
  771.         switch (*regparse) {
  772.         case 'w':
  773.             ret = regnode(ALNUM);
  774.             *flagp |= HASWIDTH|SIMPLE;
  775.             regparse++;
  776.             break;
  777.         case 'W':
  778.             ret = regnode(NALNUM);
  779.             *flagp |= HASWIDTH|SIMPLE;
  780.             regparse++;
  781.             break;
  782.         case 'b':
  783.             ret = regnode(BOUND);
  784.             *flagp |= SIMPLE;
  785.             regparse++;
  786.             break;
  787.         case 'B':
  788.             ret = regnode(NBOUND);
  789.             *flagp |= SIMPLE;
  790.             regparse++;
  791.             break;
  792.         case 's':
  793.             ret = regnode(SPACE);
  794.             *flagp |= HASWIDTH|SIMPLE;
  795.             regparse++;
  796.             break;
  797.         case 'S':
  798.             ret = regnode(NSPACE);
  799.             *flagp |= HASWIDTH|SIMPLE;
  800.             regparse++;
  801.             break;
  802.         case 'd':
  803.             ret = regnode(DIGIT);
  804.             *flagp |= HASWIDTH|SIMPLE;
  805.             regparse++;
  806.             break;
  807.         case 'D':
  808.             ret = regnode(NDIGIT);
  809.             *flagp |= HASWIDTH|SIMPLE;
  810.             regparse++;
  811.             break;
  812.         case 'n':
  813.         case 'r':
  814.         case 't':
  815.         case 'f':
  816.         case 'e':
  817.         case 'a':
  818.         case 'x':
  819.         case 'c':
  820.         case '0':
  821.             goto defchar;
  822.         case '1': case '2': case '3': case '4':
  823.         case '5': case '6': case '7': case '8': case '9':
  824.             {
  825.                 int num = atoi(regparse);
  826.  
  827.  
  828.                 if (num > 9 && num >= regnpar)
  829.                 goto defchar;
  830.                 else {
  831.                 regsawback = 1;
  832.                 ret = reganode(REF, num);
  833.                 while (isDIGIT(*regparse))
  834.                     regparse++;
  835.                 *flagp |= SIMPLE;
  836.                 }
  837.             }
  838.             break;
  839.         case '\0':
  840.             if (regparse >= regxend)
  841.                 FAIL("trailing \\ in regexp");
  842.             /* FALL THROUGH */
  843.         default:
  844.             goto defchar;
  845.         }
  846.         break;
  847.     default: {
  848.             register int len;
  849.             register char ender;
  850.             register char *p;
  851.             char *oldp;
  852.             int numlen;
  853.  
  854.  
  855.             defchar:
  856.             ret = regnode(EXACTLY);
  857.             regc(0);        /* save spot for len */
  858.             for (len=0, p=regparse-1;
  859.               len < 127 && p < regxend;
  860.               len++)
  861.             {
  862.                 oldp = p;
  863.                 switch (*p) {
  864.                 case '^':
  865.                 case '$':
  866.                 case '.':
  867.                 case '[':
  868.                 case '(':
  869.                 case ')':
  870.                 case '|':
  871.                 goto loopdone;
  872.                 case '\\':
  873.                 switch (*++p) {
  874.                 case 'w':
  875.                 case 'W':
  876.                 case 'b':
  877.                 case 'B':
  878.                 case 's':
  879.                 case 'S':
  880.                 case 'd':
  881.                 case 'D':
  882.                     --p;
  883.                     goto loopdone;
  884.                 case 'n':
  885.                     ender = '\n';
  886.                     p++;
  887.                     break;
  888.                 case 'r':
  889.                     ender = '\r';
  890.                     p++;
  891.                     break;
  892.                 case 't':
  893.                     ender = '\t';
  894.                     p++;
  895.                     break;
  896.                 case 'f':
  897.                     ender = '\f';
  898.                     p++;
  899.                     break;
  900.                 case 'e':
  901.                     ender = '\033';
  902.                     p++;
  903.                     break;
  904.                 case 'a':
  905.                     ender = '\007';
  906.                     p++;
  907.                     break;
  908.                 case 'x':
  909.                     ender = scanhex(++p, 2, &numlen);
  910.                     p += numlen;
  911.                     break;
  912.                 case 'c':
  913.                     p++;
  914.                     ender = *p++;
  915.                     if (isLOWER(ender))
  916.                     ender = toupper(ender);
  917.                     ender ^= 64;
  918.                     break;
  919.                 case '0': case '1': case '2': case '3':case '4':
  920.                 case '5': case '6': case '7': case '8':case '9':
  921.                     if (*p == '0' ||
  922.                       (isDIGIT(p[1]) && atoi(p) >= regnpar) ) {
  923.                     ender = scanoct(p, 3, &numlen);
  924.                     p += numlen;
  925.                     }
  926.                     else {
  927.                     --p;
  928.                     goto loopdone;
  929.                     }
  930.                     break;
  931.                 case '\0':
  932.                     if (p >= regxend)
  933.                     FAIL("trailing \\ in regexp");
  934.                     /* FALL THROUGH */
  935.                 default:
  936.                     ender = *p++;
  937.                     break;
  938.                 }
  939.                 break;
  940.                 default:
  941.                 ender = *p++;
  942.                 break;
  943.                 }
  944.                 if (regfold && isUPPER(ender))
  945.                     ender = tolower(ender);
  946.                 if (ISMULT2(p)) { /* Back off on ?+*. */
  947.                 if (len)
  948.                     p = oldp;
  949.                 else {
  950.                     len++;
  951.                     regc(ender);
  952.                 }
  953.                 break;
  954.                 }
  955.                 regc(ender);
  956.             }
  957.             loopdone:
  958.             regparse = p;
  959.             if (len <= 0)
  960.                 FAIL("internal disaster in regexp");
  961.             *flagp |= HASWIDTH;
  962.             if (len == 1)
  963.                 *flagp |= SIMPLE;
  964.             if (regcode != ®dummy)
  965.                 *OPERAND(ret) = len;
  966.             regc('\0');
  967.         }
  968.         break;
  969.     }
  970.  
  971.  
  972.     return(ret);
  973. }
  974.  
  975.  
  976. static void
  977. regset(bits,def,c)
  978. char *bits;
  979. int def;
  980. register int c;
  981. {
  982.     if (regcode == ®dummy)
  983.         return;
  984.     c &= 255;
  985.     if (def)
  986.         bits[c >> 3] &= ~(1 << (c & 7));
  987.     else
  988.         bits[c >> 3] |=  (1 << (c & 7));
  989. }
  990.  
  991.  
  992. static char *
  993. regclass()
  994. {
  995.     register char *bits;
  996.     register int class;
  997.     register int lastclass;
  998.     register int range = 0;
  999.     register char *ret;
  1000.     register int def;
  1001.     int numlen;
  1002.  
  1003.  
  1004.     ret = regnode(ANYOF);
  1005.     if (*regparse == '^') {    /* Complement of range. */
  1006.         regparse++;
  1007.         def = 0;
  1008.     } else {
  1009.         def = 255;
  1010.     }
  1011.     bits = regcode;
  1012.     for (class = 0; class < 32; class++)
  1013.         regc(def);
  1014.     if (*regparse == ']' || *regparse == '-')
  1015.         goto skipcond;        /* allow 1st char to be ] or - */
  1016.     while (regparse < regxend && *regparse != ']') {
  1017.           skipcond:
  1018.         class = UCHARAT(regparse++);
  1019.         if (class == '\\') {
  1020.             class = UCHARAT(regparse++);
  1021.             switch (class) {
  1022.             case 'w':
  1023.                 for (class = 'a'; class <= 'z'; class++)
  1024.                     regset(bits,def,class);
  1025.                 for (class = 'A'; class <= 'Z'; class++)
  1026.                     regset(bits,def,class);
  1027.                 for (class = '0'; class <= '9'; class++)
  1028.                     regset(bits,def,class);
  1029.                 regset(bits,def,'_');
  1030.                 lastclass = 1234;
  1031.                 continue;
  1032.             case 's':
  1033.                 regset(bits,def,' ');
  1034.                 regset(bits,def,'\t');
  1035.                 regset(bits,def,'\r');
  1036.                 regset(bits,def,'\f');
  1037.                 regset(bits,def,'\n');
  1038.                 lastclass = 1234;
  1039.                 continue;
  1040.             case 'd':
  1041.                 for (class = '0'; class <= '9'; class++)
  1042.                     regset(bits,def,class);
  1043.                 lastclass = 1234;
  1044.                 continue;
  1045.             case 'n':
  1046.                 class = '\n';
  1047.                 break;
  1048.             case 'r':
  1049.                 class = '\r';
  1050.                 break;
  1051.             case 't':
  1052.                 class = '\t';
  1053.                 break;
  1054.             case 'f':
  1055.                 class = '\f';
  1056.                 break;
  1057.             case 'b':
  1058.                 class = '\b';
  1059.                 break;
  1060.             case 'e':
  1061.                 class = '\033';
  1062.                 break;
  1063.             case 'a':
  1064.                 class = '\007';
  1065.                 break;
  1066.             case 'x':
  1067.                 class = scanhex(regparse, 2, &numlen);
  1068.                 regparse += numlen;
  1069.                 break;
  1070.             case 'c':
  1071.                 class = *regparse++;
  1072.                 if (isLOWER(class))
  1073.                     class = toupper(class);
  1074.                 class ^= 64;
  1075.                 break;
  1076.             case '0': case '1': case '2': case '3': case '4':
  1077.             case '5': case '6': case '7': case '8': case '9':
  1078.                 class = scanoct(--regparse, 3, &numlen);
  1079.                 regparse += numlen;
  1080.                 break;
  1081.             }
  1082.         }
  1083.         if (range) {
  1084.             if (lastclass > class)
  1085.                 FAIL("invalid [] range in regexp");
  1086.             range = 0;
  1087.         }
  1088.         else {
  1089.             lastclass = class;
  1090.             if (*regparse == '-' && regparse+1 < regxend &&
  1091.                 regparse[1] != ']') {
  1092.                 regparse++;
  1093.                 range = 1;
  1094.                 continue;    /* do it next time */
  1095.             }
  1096.         }
  1097.         for ( ; lastclass <= class; lastclass++) {
  1098.             regset(bits,def,lastclass);
  1099.             if (regfold && isUPPER(lastclass))
  1100.                 regset(bits,def,tolower(lastclass));
  1101.         }
  1102.         lastclass = class;
  1103.     }
  1104.     if (*regparse != ']')
  1105.         FAIL("unmatched [] in regexp");
  1106.     regparse++;
  1107.     return ret;
  1108. }
  1109.  
  1110.  
  1111. /*
  1112.  - regnode - emit a node
  1113.  */
  1114. static char *            /* Location. */
  1115. regnode(op)
  1116. char op;
  1117. {
  1118.     register char *ret;
  1119.     register char *ptr;
  1120.  
  1121.  
  1122.     ret = regcode;
  1123.     if (ret == ®dummy) {
  1124. #ifdef REGALIGN
  1125.         if (!(regsize & 1))
  1126.             regsize++;
  1127. #endif
  1128.         regsize += 3;
  1129.         return(ret);
  1130.     }
  1131.  
  1132.  
  1133. #ifdef REGALIGN
  1134. #ifndef lint
  1135.     if (!((long)ret & 1))
  1136.         *ret++ = 127;
  1137. #endif
  1138. #endif
  1139.     ptr = ret;
  1140.     *ptr++ = op;
  1141.     *ptr++ = '\0';        /* Null "next" pointer. */
  1142.     *ptr++ = '\0';
  1143.     regcode = ptr;
  1144.  
  1145.  
  1146.     return(ret);
  1147. }
  1148.  
  1149.  
  1150. /*
  1151.  - reganode - emit a node with an argument
  1152.  */
  1153. static char *            /* Location. */
  1154. reganode(op, arg)
  1155. char op;
  1156. unsigned short arg;
  1157. {
  1158.     register char *ret;
  1159.     register char *ptr;
  1160.  
  1161.  
  1162.     ret = regcode;
  1163.     if (ret == ®dummy) {
  1164. #ifdef REGALIGN
  1165.         if (!(regsize & 1))
  1166.             regsize++;
  1167. #endif
  1168.         regsize += 5;
  1169.         return(ret);
  1170.     }
  1171.  
  1172.  
  1173. #ifdef REGALIGN
  1174. #ifndef lint
  1175.     if (!((long)ret & 1))
  1176.         *ret++ = 127;
  1177. #endif
  1178. #endif
  1179.     ptr = ret;
  1180.     *ptr++ = op;
  1181.     *ptr++ = '\0';        /* Null "next" pointer. */
  1182.     *ptr++ = '\0';
  1183. #ifdef REGALIGN
  1184.     *(unsigned short *)(ret+3) = arg;
  1185. #else
  1186.     ret[3] = arg >> 8; ret[4] = arg & 0377;
  1187. #endif
  1188.     ptr += 2;
  1189.     regcode = ptr;
  1190.  
  1191.  
  1192.     return(ret);
  1193. }
  1194.  
  1195.  
  1196. /*
  1197.  - regc - emit (if appropriate) a byte of code
  1198.  */
  1199. static void
  1200. regc(b)
  1201. char b;
  1202. {
  1203.     if (regcode != ®dummy)
  1204.         *regcode++ = b;
  1205.     else
  1206.         regsize++;
  1207. }
  1208.  
  1209.  
  1210. /*
  1211.  - reginsert - insert an operator in front of already-emitted operand
  1212.  *
  1213.  * Means relocating the operand.
  1214.  */
  1215. static void
  1216. reginsert(op, opnd)
  1217. char op;
  1218. char *opnd;
  1219. {
  1220.     register char *src;
  1221.     register char *dst;
  1222.     register char *place;
  1223.     register offset = (op == CURLY ? 4 : 0);
  1224.  
  1225.  
  1226.     if (regcode == ®dummy) {
  1227. #ifdef REGALIGN
  1228.         regsize += 4 + offset;
  1229. #else
  1230.         regsize += 3 + offset;
  1231. #endif
  1232.         return;
  1233.     }
  1234.  
  1235.  
  1236.     src = regcode;
  1237. #ifdef REGALIGN
  1238.     regcode += 4 + offset;
  1239. #else
  1240.     regcode += 3 + offset;
  1241. #endif
  1242.     dst = regcode;
  1243.     while (src > opnd)
  1244.         *--dst = *--src;
  1245.  
  1246.  
  1247.     place = opnd;        /* Op node, where operand used to be. */
  1248.     *place++ = op;
  1249.     *place++ = '\0';
  1250.     *place++ = '\0';
  1251.     while (offset-- > 0)
  1252.         *place++ = '\0';
  1253. }
  1254.  
  1255.  
  1256. /*
  1257.  - regtail - set the next-pointer at the end of a node chain
  1258.  */
  1259. static void
  1260. regtail(p, val)
  1261. char *p;
  1262. char *val;
  1263. {
  1264.     register char *scan;
  1265.     register char *temp;
  1266.     register int offset;
  1267.  
  1268.  
  1269.     if (p == ®dummy)
  1270.         return;
  1271.  
  1272.  
  1273.     /* Find last node. */
  1274.     scan = p;
  1275.     for (;;) {
  1276.         temp = regnext(scan);
  1277.         if (temp == NULL)
  1278.             break;
  1279.         scan = temp;
  1280.     }
  1281.  
  1282.  
  1283. #ifdef REGALIGN
  1284.     offset = val - scan;
  1285. #ifndef lint
  1286.     *(short*)(scan+1) = offset;
  1287. #else
  1288.     offset = offset;
  1289. #endif
  1290. #else
  1291.     if (OP(scan) == BACK)
  1292.         offset = scan - val;
  1293.     else
  1294.         offset = val - scan;
  1295.     *(scan+1) = (offset>>8)&0377;
  1296.     *(scan+2) = offset&0377;
  1297. #endif
  1298. }
  1299.  
  1300.  
  1301. /*
  1302.  - regoptail - regtail on operand of first argument; nop if operandless
  1303.  */
  1304. static void
  1305. regoptail(p, val)
  1306. char *p;
  1307. char *val;
  1308. {
  1309.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  1310.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  1311.         return;
  1312.     regtail(NEXTOPER(p), val);
  1313. }
  1314.  
  1315.  
  1316. /*
  1317.  - regcurly - a little FSA that accepts {\d+,?\d*}
  1318.  */
  1319. STATIC int
  1320. regcurly(s)
  1321. register char *s;
  1322. {
  1323.     if (*s++ != '{')
  1324.     return FALSE;
  1325.     if (!isDIGIT(*s))
  1326.     return FALSE;
  1327.     while (isDIGIT(*s))
  1328.     s++;
  1329.     if (*s == ',')
  1330.     s++;
  1331.     while (isDIGIT(*s))
  1332.     s++;
  1333.     if (*s != '}')
  1334.     return FALSE;
  1335.     return TRUE;
  1336. }
  1337.  
  1338.  
  1339. #ifdef DEBUGGING
  1340.  
  1341.  
  1342. /*
  1343.  - regdump - dump a regexp onto stderr in vaguely comprehensible form
  1344.  */
  1345. void
  1346. regdump(r)
  1347. regexp *r;
  1348. {
  1349.     register char *s;
  1350.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1351.     register char *next;
  1352.  
  1353.  
  1354.  
  1355.  
  1356.     s = r->program + 1;
  1357.     while (op != END) {    /* While that wasn't END last time... */
  1358. #ifdef REGALIGN
  1359.         if (!((long)s & 1))
  1360.             s++;
  1361. #endif
  1362.         op = OP(s);
  1363.         fprintf(stderr,"%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1364.         next = regnext(s);
  1365.         s += regarglen[op];
  1366.         if (next == NULL)        /* Next ptr. */
  1367.             fprintf(stderr,"(0)");
  1368.         else
  1369.             fprintf(stderr,"(%d)", (s-r->program)+(next-s));
  1370.         s += 3;
  1371.         if (op == ANYOF) {
  1372.             s += 32;
  1373.         }
  1374.         if (op == EXACTLY) {
  1375.             /* Literal string, where present. */
  1376.             s++;
  1377.             while (*s != '\0') {
  1378.                 (void)putchar(*s);
  1379.                 s++;
  1380.             }
  1381.             s++;
  1382.         }
  1383.         (void)putchar('\n');
  1384.     }
  1385.  
  1386.  
  1387.     /* Header fields of interest. */
  1388.     if (r->regstart)
  1389.         fprintf(stderr,"start `%s' ", r->regstart->str_ptr);
  1390.     if (r->regstclass)
  1391.         fprintf(stderr,"stclass `%s' ", regprop(r->regstclass));
  1392.     if (r->reganch & ROPT_ANCH)
  1393.         fprintf(stderr,"anchored ");
  1394.     if (r->reganch & ROPT_SKIP)
  1395.         fprintf(stderr,"plus ");
  1396.     if (r->reganch & ROPT_IMPLICIT)
  1397.         fprintf(stderr,"implicit ");
  1398.     if (r->regmust != NULL)
  1399.         fprintf(stderr,"must have \"%s\" back %d ", r->regmust->str_ptr,
  1400.           r->regback);
  1401.     fprintf(stderr, "minlen %d ", r->minlen);
  1402.     fprintf(stderr,"\n");
  1403. }
  1404.  
  1405.  
  1406. /*
  1407.  - regprop - printable representation of opcode
  1408.  */
  1409. char *
  1410. regprop(op)
  1411. char *op;
  1412. {
  1413.     register char *p;
  1414.  
  1415.  
  1416.     (void) strcpy(buf, ":");
  1417.  
  1418.  
  1419.     switch (OP(op)) {
  1420.     case BOL:
  1421.         p = "BOL";
  1422.         break;
  1423.     case EOL:
  1424.         p = "EOL";
  1425.         break;
  1426.     case ANY:
  1427.         p = "ANY";
  1428.         break;
  1429.     case ANYOF:
  1430.         p = "ANYOF";
  1431.         break;
  1432.     case BRANCH:
  1433.         p = "BRANCH";
  1434.         break;
  1435.     case EXACTLY:
  1436.         p = "EXACTLY";
  1437.         break;
  1438.     case NOTHING:
  1439.         p = "NOTHING";
  1440.         break;
  1441.     case BACK:
  1442.         p = "BACK";
  1443.         break;
  1444.     case END:
  1445.         p = "END";
  1446.         break;
  1447.     case ALNUM:
  1448.         p = "ALNUM";
  1449.         break;
  1450.     case NALNUM:
  1451.         p = "NALNUM";
  1452.         break;
  1453.     case BOUND:
  1454.         p = "BOUND";
  1455.         break;
  1456.     case NBOUND:
  1457.         p = "NBOUND";
  1458.         break;
  1459.     case SPACE:
  1460.         p = "SPACE";
  1461.         break;
  1462.     case NSPACE:
  1463.         p = "NSPACE";
  1464.         break;
  1465.     case DIGIT:
  1466.         p = "DIGIT";
  1467.         break;
  1468.     case NDIGIT:
  1469.         p = "NDIGIT";
  1470.         break;
  1471.     case CURLY:
  1472.         (void)sprintf(buf+strlen(buf), "CURLY {%d,%d}",
  1473.             ARG1(op),ARG2(op));
  1474.         p = NULL;
  1475.         break;
  1476.     case REF:
  1477.         (void)sprintf(buf+strlen(buf), "REF%d", ARG1(op));
  1478.         p = NULL;
  1479.         break;
  1480.     case OPEN:
  1481.         (void)sprintf(buf+strlen(buf), "OPEN%d", ARG1(op));
  1482.         p = NULL;
  1483.         break;
  1484.     case CLOSE:
  1485.         (void)sprintf(buf+strlen(buf), "CLOSE%d", ARG1(op));
  1486.         p = NULL;
  1487.         break;
  1488.     case STAR:
  1489.         p = "STAR";
  1490.         break;
  1491.     case PLUS:
  1492.         p = "PLUS";
  1493.         break;
  1494.     default:
  1495.         FAIL("corrupted regexp opcode");
  1496.     }
  1497.     if (p != NULL)
  1498.         (void) strcat(buf, p);
  1499.     return(buf);
  1500. }
  1501. #endif /* DEBUGGING */
  1502.  
  1503.  
  1504. regfree(r)
  1505. struct regexp *r;
  1506. {
  1507.     if (r->precomp) {
  1508.         Safefree(r->precomp);
  1509.         r->precomp = Nullch;
  1510.     }
  1511.     if (r->subbase) {
  1512.         Safefree(r->subbase);
  1513.         r->subbase = Nullch;
  1514.     }
  1515.     if (r->regmust) {
  1516.         str_free(r->regmust);
  1517.         r->regmust = Nullstr;
  1518.     }
  1519.     if (r->regstart) {
  1520.         str_free(r->regstart);
  1521.         r->regstart = Nullstr;
  1522.     }
  1523.     Safefree(r->startp);
  1524.     Safefree(r->endp);
  1525.     Safefree(r);
  1526. }
  1527.